#include <iostream>
#include <vector>

/*
Given an all-positive array A, find the max product from all possible trains
Train A[i]...A[j] i <= j
A = { 1, 3, 4, 0.9, 10 } -> 108
i = 1
j = 3
A[i]...A[j] => A[1]...A[3] => A[1],A[2],A[3] => { 3, 4, 0.9} => 3 * 4 * 0.9 = 10.8
// better than O(n*n)
*/

using namespace std;

#if 1
// Running time: O(n)
double foo(vector<double> &input) {
    int len = input.size();
    if (!len) return 0.0; // empty array
    double maxproduct = 0.0, max_current = input[0];
    for (int i = 1; i < len; i++) {
        max_current = max(max_current*input[i], input[i]);
        if (max_current > maxproduct) maxproduct = max_current;
    }
    return maxproduct;
}
#else
// Running time: O(n)
double foo(vector<double> input) {
    int len = input.size();
    if (!len) return 0.0; // empty array
    // initialize product array with the same size as input
    vector<double> product(len);
    product[0] = input[0];
    for (int i = 1; i < len; i++) {
        product[i] = max(product[i-1]*input[i], input[i]);
    }
    double maxproduct = 0.0;
    for (int i = 0; i < len; i++) {
        if (product[i] > maxproduct) maxproduct = product[i];
    }
    return maxproduct;
}
#endif

int main() {
    double test0[] = {1, 3, 4, 0.9, 10};
    double test1[] = {1, 3, 4, 0.01, 10, 10, 0.001};
    double test2[] = {1, 3, 4, 0.1, 10, 10, 0.001};
    double test3[] = {1, 3, 4, 0.01, 10};
    vector<double> vtest0(test0, test0 + sizeof(test0)/sizeof(double));
    vector<double> vtest1(test1, test1 + sizeof(test1)/sizeof(double));
    vector<double> vtest2(test2, test2 + sizeof(test2)/sizeof(double));
    vector<double> vtest3(test3, test3 + sizeof(test3)/sizeof(double));

    double res0 = foo(vtest0);
    cout << "max of test0: " << res0 << endl;

    double res1 = foo(vtest1);
    cout << "max of test1: " << res1 << endl;

    double res2 = foo(vtest2);
    cout << "max of test2: " << res2 << endl;

    double res3 = foo(vtest3);
    cout << "max of test3: " << res3 << endl;

    return 0;
}
